package link;

/**
 * leetcode 92
 *
 */
public class ReversePart {

    public static void main(String[] args) {
        int a = findKthNumber(196,45);
    }

    public static int[] exchange(int[] nums) {
        if(nums.length == 0){
            return nums;
        }
        int j = nums.length - 1;
        int i = 0;
        while( i < j ){
            if(isOd(nums[i])){
                while(j > i){
                    if(!isOd(nums[j])){
                        int temp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = temp;
                        break;
                    }
                    j++;
                }
            }
            i++;
        }
        return nums;
    }

    private static boolean isOd(int num){
        return num%2 > 0 ? true:false;
    }

    public static int findKthNumber(int n, int k) {
        int cur = 1;
        k = k -1;
        while (k > 0) {
            int num = getNode(n, cur);
            if (num <= k) {
                cur += 1;
                k -= num;
            } else {
                cur *= 10;
                k -= 1;
            }
        }
        return cur;
    }

    private static int getNode(int n, long first) {
        int num = 0;
        int floor = 0;
        while(first <= n){
            if((n + 1) / (int)Math.pow(10,floor) > 1){
                num += (int)Math.pow(10,floor);
            }else{
                num += (n + 1) - (int)Math.pow(10,floor);
            }
            first *= 10;
            floor++;
        }
        return num;
    }

//    private static int getNode(int n,int prefix) {
//        int count = 0;
//        int nextPrefix = prefix + 1;
//        while(prefix <= n) {
//            count += Math.min(n + 1, nextPrefix) - prefix;//计算当层的结点数目
//            if(prefix <= n / 10) {//防止溢出（如果将prefix和nextPrefix设置long型的话不用作此判断）
//                prefix *= 10;
//                nextPrefix *= 10;
//            } else {
//                break;
//            }
//        }
//        return count;
//    }

}
